package com.test.course.array;

/**
 * @author sujiafa
 * @date 2025/7/3
 */
public class 希尔排序 {

    public static void shellSort(int[] arr) {
        // 对数组元素进行分组，同一个gap的元素进行插入排序
        int gap = arr.length / 2;
        while (gap > 0) {
            // 对每组元素进行插入排序
            for (int i = gap; i < arr.length; i++) {
                // temp 为每组中无序数组第 1 个元素
                int temp = arr[i];
                int j = i;
                // 从右至左遍历每组中的有序数组元素，注意终止条件是j >= gap，因为前一个元素为第一个元素
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            gap = gap / 2;
        }
    }

    public static void main(String[] args) {
        // 测试用例1：随机顺序
        int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前的数组：");
        printArray(arr1);
        shellSort(arr1);
        System.out.println("排序后的数组：");
        printArray(arr1);
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
